In multi-threaded programs, protecting some portions and/or variables of a program from being accessed by multiple threads is desirable. In one approach using a lock mechanism, a thread, in accessing a protected portion, acquires a lock and thus prevents other threads from accessing the same portion during the time the thread retains the lock. When the thread releases the lock, another thread may acquire the lock to access the protected portion and prevent other threads from accessing the same portion.
A thread waiting for the lock may be put in a sleep queue and transferred to a run queue when this waiting thread is ready to execute. However, transferring a thread between the sleep queue and the run queue is usually expensive. Approaches have been developed in which the waiting threads execute some spin-yield cycles before being transferred to the sleep queue. In these approaches, a waiting thread, while waiting for a lock, spins on a processor for a few cycles, then tries to acquire the lock. If the thread cannot acquire the lock, then the thread yields the processor, i.e., makes it available for use by other threads. The waiting thread repeats the spin-yield cycles for a few times up to a threshold, at which time the waiting thread is put into the sleep queue. Experience shows that the waiting threads can usually acquire the lock in a few tries without being transferred to the sleep queue.
However, in various situations such as in applications in which lock contention is heavy and/or the thread holds on to the lock for a long time, the spin-yield threads in many cases are eventually put to the sleep queue. During the spin-yield time, the processors performing the spin-yield cycle cannot accomplish other useful work, and the spin-yield threads may generate a lot of expensive system calls. In symmetric multiple processor systems with many processors, this effect can be pronounced.
Based on the foregoing, it is desirable that mechanisms be provided to solve the above deficiencies and related problems.